package leetcode.ArrayAndString;

import java.util.Arrays;

public class FindDiagonalOrder {

    /**
     * 给定一个含有 M x N 个元素的矩阵（M 行，N 列），请以对角线遍历的顺序返回这个矩阵中的所有元素
     * @param matrix
     * @return
     */
    public static int[] findDiagonalOrder(int[][] matrix) {


        int[] result = new int[0];

        if (matrix == null || matrix.length == 0) {
            return result;
        }
        boolean status = true;

        int hight = matrix.length;
        int weight = matrix[0].length;
        result = new int[hight * weight];

        int resultIndex = 0;
        int x = 0;
        int y = 0;
        for (int i = 0; i < hight * weight; i++) {
            result[resultIndex++] = matrix[y][x];
            if (status) {  //右上移动
                x++;
                y--;
                if (x == weight) {
                    status = !status;
                    x--;
                    y++;
                    y++;
                }

                if (y < 0) {
                    status = !status;
                    y++;
                }

            } else { //左下移动
                x--;
                y++;
                if (y == hight) {
                    status = !status;
                    y--;
                    x++;
                    x++;
                }
                if (x < 0) {
                    status = !status;
                    x++;
                }
            }
        }
        return result;
    }

    public static void main(String args[]) {
        int[][] nums = addList();
        long start = System.currentTimeMillis();
        System.out.println(Arrays.toString(findDiagonalOrder(nums)));
        long end = System.currentTimeMillis();

        System.out.println("time = " + (end - start));

    }

    private static int[][] addList() {
        int[][] bb = {};
        return bb;
    }


}
